#include "huffman.h"
#include<iostream>

typedef const ChildNode* const  C_CHILDNODE_POINT;
typedef std::multiset<ChildNode*,bool(*)(C_CHILDNODE_POINT &,C_CHILDNODE_POINT&)> TREESET;

bool compareByNum(C_CHILDNODE_POINT &lhs,C_CHILDNODE_POINT &rhs)
{
	if(lhs->n<rhs->n)
		return true;
	return false;
}

RootNode* buildTree(const char  *c)
{

	unsigned nums[256];
	for(int i =0;i<256;++i)
	{
		nums[i] = 0;
	}

	unsigned  len = strlen(c);
	for(unsigned i=0;i<len;++i)
	{
		nums[c[i]]++;
	}
	//bool(*g)(const ChildNode*&,const ChildNode*&)= compareByNum;

	TREESET nodeSet(&compareByNum);
	for(int i =0;i<256;++i)
	{
		if(nums[i])
		{
			ChildNode *child = new ChildNode((const char)i,nums[i]);
			nodeSet.insert(child);
		}
	}



	while(nodeSet.size()>1)
	{
        std::cout<<"-----------------"<<std::endl;
        TREESET::iterator first = nodeSet.begin();
        ChildNode * left = *(nodeSet.begin());
        nodeSet.erase(nodeSet.begin());
        ChildNode * right = *(nodeSet.begin());
        nodeSet.erase(nodeSet.begin());
        ParentNode *parent = new ParentNode(left,right);
        nodeSet.insert(parent);



	}



	RootNode *root = new RootNode();


	root->root = *nodeSet.begin();

	LOGW("@@end buildTree");

	return root;
}

void recursionTable(ChildNode *&child,std::string& codes,int index,std::list<CodeTable*> *&table)
{


	if(typeid(*child)==typeid(ParentNode))
	{
		ParentNode* parent = (ParentNode*) child;
		ChildNode *left = parent->left;
		if(left!=NULL)
		{

			codes.replace(index,1,1,'0');
			recursionTable(left,codes,index+1,table);
		}

		ChildNode *right = parent->right;
		if(right!=NULL)
		{
			codes.replace(index,1,1,'1');
			recursionTable(right,codes,index+1,table);
		}

	}
	else
	{
		CodeTable *codetable = new CodeTable();
		codetable->code = codes.substr(0,index);
		codetable->node = child;
		table->push_back(codetable);

	}
}

std::list<CodeTable*> * makeTable(RootNode* &root)
{
	std::list<CodeTable*> *table = new std::list<CodeTable*>();
	std::string code;
	recursionTable(root->root,code,0,table);

	LOGW("@@end makeTable");
	return table;
}
std::string transcoding(std::list<CodeTable*> *&table,const char *c)
{
	unsigned len = strlen(c);
	std::string result;
	for(int i =0;i<len;++i)
	{
		std::list<CodeTable*>::iterator start = table->begin();
		std::list<CodeTable*>::iterator end = table->end();
		const char &cu = c[i];
		while(start!=end)
		{
			if((*start)->node->c==cu)
			{
				result+=(*start)->code;
				break;
			}
			else
			{
				++start;
			}

		}
	}
	LOGW("@@end transcoding");
	return result;
}

std::string decoding(RootNode* &root,const char *c)
{
	std::string result;
	ChildNode *child = root->root;
	unsigned len = strlen(c);
	for(unsigned i = 0;i<len;++i)
	{
		if(typeid(*child)==typeid(ParentNode))
		{
			ParentNode *parent = (ParentNode*)child;
			const char &cc = c[i];
			if(cc=='0')
			{
				child = parent->left;
			}
			else
			{
				child = parent->right;
			}
			if(typeid(*child)!=typeid(ParentNode))
			{
				result+=child->c;
				child = root->root;
			}
		}
		else
		{
			result+=child->c;
			child = root->root;
		}
	}
	LOGW("@@end decoding");
	return result;
}